package com.gozap.dynmicrogram.example;

import java.util.ArrayList;
import java.util.Calendar;
import java.util.List;

/**
 * 机器，动态规划，计算汽车零件如何从两条工作连上工作最合适
 * 
 * @author yaoming
 * @date 2013-1-14 下午05:54:24
 * @since JDK1.6
 * @version 2.0.0
 */
public class Machine {
	// 链上工作时间
	private int[] line1 = { 7, 9, 3, 4, 8, 4 };
	private int[] line2 = { 8, 5, 6, 4, 5, 7 };
	// // 链上工作时间修改为最后时间都为0
	// private int[] line1 = { 3, 6, 2, 7, 3, 8, 0 };
	// private int[] line2 = { 4, 2, 5, 3, 6, 8, 0 };

	// 从此链出需要时间，其中第一个数据为进入此链时间
	private int[] t1 = { 2, 2, 3, 1, 3, 4, 3 };
	private int[] t2 = { 4, 2, 1, 2, 2, 1, 2 };

	// 两条生产线
	int lines = 2;
	// 每条链6个环节
	int segments = 6;

	/**
	 * 最小路径时间
	 */
	public int[][] minWay() {

		// 存储通过某节点最小时间
		int[][] min = new int[lines][segments];

		// 记录步骤
		int[][] record = new int[lines][segments];

		min[0][0] = t1[0] + line1[0];
		min[1][0] = t2[0] + line2[0];

		int a;
		int b;
		for (int i = 1; i < segments; i++) {
			// 计算链0上的
			a = min[0][i - 1] + line1[i];
			b = min[1][i - 1] + t2[i] + line1[i];
			if (b < a) {
				min[0][i] = b;
				record[0][i - 1] = 1;
			} else {
				min[0][i] = a;
				record[0][i - 1] = 0;
			}
			// 计算链1上的
			a = min[0][i - 1] + t1[i] + line2[i];
			b = min[1][i - 1] + line2[i];
			if (b < a) {
				min[1][i] = b;
				record[1][i - 1] = 1;
			} else {
				min[1][i] = a;
				record[1][i - 1] = 0;
			}
		}
		a = min[0][segments - 1] + t1[segments];
		b = min[1][segments - 1] + t2[segments];
		if (b < a) {
			record[0][segments - 1] = 1;
			record[1][segments - 1] = 1;
		} else {
			record[0][segments - 1] = 0;
			record[1][segments - 1] = 0;
		}
		return record;
	}

	public void printRecord(int[][] record) {
		List<Integer> result = new ArrayList<Integer>();

		int a = 0;
		for (int i = segments - 1; i >= 0; i--) {
			a = record[a][i];
			result.add(a);
		}
		print(result);

	}

	public void print(List<Integer> list) {
		int len = list.size();
		for (int i = len - 1; i >= 0; i--) {
			System.out.print((list.get(i) + 1) + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		Machine machine = new Machine();
		// 121221
		machine.printRecord(machine.minWay());

		Calendar c = Calendar.getInstance();
		c.setTimeInMillis(973468800L * 1000L);
		System.out.println(c.get(Calendar.YEAR) + " " + c.get(Calendar.MONTH));
	}
}
